class Solution {
public:
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
    bool dfs(vector<vector<char>>& board,string& word,int x,int y,int index)
    {
        if(board[x][y]!=word[index])
        {
            return false;
        }
        if(index==word.size()-1)
        {
            return true;//找到了最后一个字符并且这个字符是符合条件的直接返回true
        }
        //说明x，y这个位置的值和word[index]这个位置的值时一样的，需要去寻找下一个位置了
        bool ret = false;
        char tmp = board[x][y];
        board[x][y] = '-1';
        for(int i = 0;i<4;i++)
        {
            int newx = x+dx[i];
            int newy = y+dy[i];
            if(newx>=0&&newx<board.size()&&newy>=0&&newy<board[0].size()&&board[newx][newy]!='-1')
            {
                bool flag = dfs(board,word,newx,newy,index+1);//递归寻找其它位置的值是否存在于这个数组中
                if(flag)
                {
                    ret = flag; 
                }
            }
        }
        board[x][y] = tmp;
        return ret;
    }
    bool exist(vector<vector<char>>& board, string word) {
        //使用dfs去数组中进行暴力搜索
        for(int i = 0;i<board.size();i++)
        {
            for(int j = 0;j<board[i].size();j++)
            {
                if(board[i][j] == word[0])
                {
                    bool ret = dfs(board,word,i,j,0);//从i，j这个位置开始往后进行宣召
                    if(ret)
                    {
                        return  true;//找到了word这个单词
                    }
                }
            }
        }
        return false;//没有找到
    }
};